#include "RedBlackTree.h"
#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } COLOR;

struct RBNode {
	ElementType data;
	struct RBNode* left, * right;
	COLOR color;
};

//销毁红黑树，采用迭代方法
static void DeleteTree(RBTree tree);
void DisposeRBTree(RBTree tree) {
	DeleteTree(tree);
}

static void DeleteTree(RBTree tree) {
	if (tree) {
		DeleteTree(tree->left);
		DeleteTree(tree->right);
		free(tree);
	}
}

/// <summary>
/// 向红黑树中插入数据，插入数据后进行调整，使之依然符合红黑树的性质
/// </summary>
/// <param name="tree">被插入数据的红黑树</param>
/// <param name="data">插入的数据</param>
/// <returns></returns>
RBTree Insert(RBTree tree, ElementType data) {
	if (!tree) {
		pRBNode newNode = (pRBNode)malloc(sizeof(struct RBNode));
		newNode->left = NULL;
		newNode->right = NULL;
		newNode->data = data;
		newNode->color = RED;
		return newNode;
	}

	Position parent = NULL;
	if (!Search(tree, data, &parent)) {
		if (data < parent->data) {
			pRBNode newNode = (pRBNode)malloc(sizeof(struct RBNode));
			newNode->left = NULL;
			newNode->right = NULL;
			newNode->data = data;
			newNode->color = RED;
			parent->left = newNode;
		} else {
			pRBNode newNode = (pRBNode)malloc(sizeof(struct RBNode));
			newNode->left = NULL;
			newNode->right = NULL;
			newNode->data = data;
			newNode->color = RED;
			parent->right = newNode;
		}
	}
	return tree;
}

/// <summary>
/// 
/// </summary>
/// <param name="tree"></param>
/// <param name="data"></param>
/// <returns></returns>
RBTree Remove(RBTree tree, ElementType data) {
	return NULL;
}

/// <summary>
/// 在红黑树中查找指定关键字，并返回相应位置。
/// </summary>
/// <param name="tree">要搜索的红黑树</param>
/// <param name="data">搜索的关键字</param>
/// <param name="pp">用以返回查到的节点的父节点（传入指针的指针，目的在于能够修改指针值)</param>
/// <returns>
/// 1、无此关键字，返回NULL
/// 2、查到该关键字，返回相应节
/// </returns>
Position Search(RBTree tree, ElementType data, Position* pp) {
	if (!tree) {
		*pp = NULL;
		return NULL;
	}
	Position temp = tree, parent = NULL;
	while (temp) {
		if (data == temp->data) {
			*pp = parent;
			return temp;
		} else if (data < temp->data) {
			parent = temp;
			temp = temp->left;
		} else {
			parent = temp;
			temp = temp->right;
		}
	}
	*pp = parent;
	return NULL;
}

void PreOrder(RBTree tree) {
	if (tree) {
		printf("%d\t", tree->data);
		PreOrder(tree->left);
		PreOrder(tree->right);
	}
}
void InOrder(RBTree tree) {
	if (tree) {
		InOrder(tree->left);
		printf("%d\t", tree->data);
		InOrder(tree->right);
	}
}
void PostOrder(RBTree tree) {
	if (tree) {
		PostOrder(tree->left);
		PostOrder(tree->right);
		printf("%d\t", tree->data);
	}
}

void TestRedBlackTree() {
	RBTree tree = NULL;
	for (int i = 0; i < 10; i++) {
		srand(i * 10);
		tree = Insert(tree, rand() % 100);
	}
	InOrder(tree);
}
